// 题目：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0？请找出所有和为 0 且不重复的三元组。
// 示例：输入 [-1,0,1,2,-1,-4] 输出 [[-1,-1,2],[-1,0,1]]

const threeSum = (nums) => {
    const res = [];
    nums.sort((a, b) => a - b); // 排序
    const len = nums.length;
    for (let i = 0; i < len - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 跳过重复
        let left = i + 1;
        let right = len - 1;
        while (left < right) {
            // 相加是否等于0
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                // 等于0，添加到数组中
                res.push([nums[i], nums[left], nums[right]]);
                // 判断是否有重复的元素
                // 把当前的左指针与它的下一个元素进行比较，如果相等，那么left指针向右移动一位
                while (left < right && nums[left] === nums[left + 1]) left++; // 跳过重复
                // 
                while (left < right && nums[right] === nums[right - 1]) right--; // 跳过重复
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}

const threeSum2 = (nums) => {
    // 批改，sort函数要传汝一个比较函数
    // nums.sort()
    nums.sort((a, b) => a - b)
    // console.log('排序后的数组：', nums);

    const result = []
    // for循环的终止条件，写成i<nums.length-2,当i到倒数第二个或最后一个时，left和right会越界
    for (let i = 0; i < nums.length - 2; i++) {
        // 对i进行去重
        if (i > 0 && nums[i] === nums[i - 1]) continue
        let left = i + 1
        let right = nums.length - 1
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right]

            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]])
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (right > left && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            }
            else if (sum > 0) {
                right--
            }
            else {
                left++
            }
        }

    }
    return result
}
const nums3 = [0, 0, -1, -1, 3, 2]
const res2 = three1Sum2(nums3)
console.log('00', res2);


// 测试用例
// let nums = [-1, 0, 1, 2, -1, -4];
// console.log(threeSum(nums)); // 输出：[ [ -1, -1, 2 ], [ -1, 0, 1 ] ]

// // 该解法时间复杂度为O(n^2)，空间复杂度为O(1)（不算输出结果）。
// // sort函数
// const array = [3, 1, 4, 1, 5, 9];
// const array2 = array.slice().sort((a, b) => a - b);
// const array3 = Array.from(array).sort((a, b) => a - b);
// console.log(array3); // 输出：[1, 1, 3, 4,


// 笔记
// 双指针的意思是：在同一个循环里（通常是while循环），同时维护两个变量（指针），它们一起行动，配合查找答案
// 比如在“三数之和”里，外循环for选第一个数，内层while循环里有left和right两个指针，分别从两头向中间靠拢，这就是典型的双指针
// 常见的双指针用法有：
// 两个指针一前一后遍历数组（如快慢指针，滑动窗口）
// 两个指针一头一尾向中间靠拢（如有序数组求和，三数之和）














// 双指针的应用场景：
// 1. 在有序数组中查找满足某种条件的元素。
// 2. 在字符串中查找满足某种条件的子串。
// 3. 在链表中查找满足某种条件的节点。
// 4. 在数组中查找满足某种条件的子数组。
// 5. 在数组中查找满足某种条件的子序列。
// 双指针的好处是：
// 1. 减少时间复杂度：双指针可以在一个循环中完成两个指针的移动，避免了嵌套循环，从而降低时间复杂度。
// 2. 减少空间复杂度：双指针通常只需要常数级的额外空间，不需要额外的数组或数据结构来存储中间结果，从而降低空间复杂度。
// 3. 提高效率：双指针可以在一个循环中完成两个指针的移动，避免了多次遍历数组，从而提高了算法的效率。
// 4. 简化代码：双指针可以使代码更简洁，易读，易于维护。通过使用双指针，可以减少代码的复杂性，使代码更易于理解和调试。  